package leetcode.code1361;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 这个贪心是错误的
 *
 * @author CaoYu
 * @date 2021年12月11日
 * @description
 */
public class Solution3 implements IDebug {

	class Union {

		private int n;
		private int[] parent;
		private int[] sizes;
		private int[] stack;

		public Union(int n) {
			this.n = n;
			this.parent = new int[n];
			this.sizes = new int[n];
			this.stack = new int[n];
			for (int i = 0; i < n; i++) {
				parent[i] = i;
				sizes[i] = 1;
			}
		}

		public int findParent(int num) {
			int root = this.parent[num];
			int p = -1;
			while (root != num) {
				this.stack[++p] = num;
				num = root;
				root = this.parent[num];
			}
			while (p > -1) {
				num = stack[p--];
				this.parent[num] = root;
			}
			return root;
		}

		public boolean isSameSet(int num1, int num2) {
			return this.findParent(num1) == this.findParent(num2);
		}

		public void union(int num1, int num2) {
			int p1 = this.findParent(num1);
			int p2 = this.findParent(num2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.parent[p1] = p2;
					this.sizes[p2] += size1;
				} else {
					this.parent[p2] = p1;
					this.sizes[p1] += size2;
				}
			}
		}

	}

	public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
		int[] parent = new int[n];
		for (int i = 0; i < n; i++) {// 设定自己为根节点
			parent[i] = -1;
		}
		for (int i = 0; i < n; i++) {// 为所有出现在leftChild，rightChild中的节点设定父节点
			int node = leftChild[i];
			if (!this.setParent(parent, node, i)) {// 双父节点的错了
				return false;
			}
			node = rightChild[i];
			if (!this.setParent(parent, node, i)) {// 双父节点的错了
				return false;
			}
		}
		int rootNum = 0;
		HelpDebug.print(parent);
		for (int i = 0; i < n; i++) {// 多个树根，错了
			int root = parent[i];
			if (root == -1) {
				rootNum++;
				if (rootNum > 1) {
					return false;
				}
			} else if (parent[root] == i) {// 双向
				return false;
			}
		}
		return rootNum == 1;// 必须有一个根
	}

	private boolean setParent(int[] parent, int node, int root) {
		if (node == -1) {
			return true;
		}
		if (parent[node] != -1) {
			return false;
		} else {
			parent[node] = root;
		}
		return true;
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug3();
//		so.debug1();
//		so.debug2();

	}

	@Override
	public void debug1() {
		HelpDebug.compare(false, this.validateBinaryTreeNodes(4, HelpDebug.str2array3("[1,0,3,-1]"), HelpDebug.str2array3("[-1,-1,-1,-1]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(true, this.validateBinaryTreeNodes(4, HelpDebug.str2array3("[1,-1,3,-1]"), HelpDebug.str2array3("[2,-1,-1,-1]")));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(false, this.validateBinaryTreeNodes(4, HelpDebug.str2array3("[1,2,0,-1]"), HelpDebug.str2array3("[-1,-1,-1,-1]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

}
